home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 11888 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.3 KB  |  67 lines
  1. Path: newsfeed.internetmci.com!iol!usenet
  2. From: David Byrden <goyra@iol.ie>
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: HELP: Algorithm for ordering (x,y) coordinates
  5. Date: 16 Mar 1996 21:55:40 GMT
  6. Organization: Ireland On-Line
  7. Message-ID: <4ifdcs$m8o@nuacht.iol.ie>
  8. References: <314B0266.456A@mit.edu>
  9. NNTP-Posting-Host: dialup-184.dublin.iol.ie
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 1.22KIT (Windows; I; 16bit)
  14.  
  15.  
  16. Imran Haq <ihaq@mit.edu> wrote:
  17. >Here is a problem that I can't seem to express in code easily using STL:
  18. >
  19. >I'm trying to order a set of (x,y) coordinates in an anitclockwise sense. To
  20. >compute whether the coordinates are indeed anticlockwise, I'm computing the
  21. >normal vector perpendicular to a plane defined by (overlapping) subsets containing
  22. >3 nodes each. If the normal vector is positive, the order is correct, otherwise
  23. >I just swap coordinate positions. 
  24. >
  25. >The problem is that I'm trying to use STL's generic sort algorithm to do this
  26. >and supplying a custom comparison function. However, the form of this function
  27. >requires only two arguments, not the 3 I need to compute order. In fact, what
  28. >I really need is to have this custom function automatically accept the 
  29. >first coordinate pair as a reference point, and modify the order of the 2nd and 3rd
  30. >points if they are not anticlockwise. 
  31. >
  32. >Any suggestions? Or do I need to write a sort algorithm outside what STL provides?
  33.  
  34.  
  35.  I think I can just about see what you are doing. I presume that there is 
  36. one fixed reference point that you use for all the triplets.
  37.  
  38.   The STL will handle this fine. What you need is to use a functor, not a 
  39. function, with the sort algorithm. A functor is an object with operator() 
  40. defined; in this case, operator() would have the same signature as the 
  41. function you have been using so far.
  42.  
  43.   The great thing is that, because a functor is an object, it can carry 
  44. around the third point within itself. A functor is rather like a fuction 
  45. with attached data.
  46.  
  47.   Here's a suggestion;
  48.  
  49.  
  50. struct clockwise{
  51.    point pt ;
  52.    clockwise( const point& p ) : pt(p) { }
  53.    bool operator() ( const point& a, const point& b )
  54.    {
  55.        return  /* some doodah involving a, b and pt */  ;
  56.    }
  57. } ;
  58.  
  59.  
  60.   sort( bunch.begin(), bunch.end(), clockwise( point( 0,0 ) ) ) ;
  61.  
  62.  
  63.                                 David
  64.  
  65.  
  66.  
  67.